package _11_整理题目._4_动态规划._跳台阶_扔鸡蛋;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/min-cost-climbing-stairs/
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
 * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 *
 * 示例 2：
 * 输入：cost = [1,100,1,1,1,100,1,1,100,1]
 * 输出：6
 * 解释：你将从下标为 0 的台阶开始。
 * - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
 * 总花费为 6 。
 *
 * 1、动态规划，自底向上：
 *      定义 dp[i] 是爬到第 i 层的最小花费，i ∈ [0,n]；
 *          则 dp[n] 为爬上长度为 n 的台阶的最小花费。
 *      初始条件
 *          dp[0] = dp[1] = 0;
 *      递推公式
 *          dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
 * 2、动态规划，滚动数组：
 * 3、自顶向下，记忆搜索
 * 4、递归
 *
 * 递归、记忆搜索、自底向上 的 核心都是 递推公式
 */
public class _02_使用最小花费爬楼梯 {

    public int minCostClimbingStairs1(int[] cost) {
        int n = cost.length;
        if(n < 2) return 0;
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        for(int i=2; i<=n; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }

    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        if(n < 2) return 0;
        int a = 0, b = 0, c = 0;
        for(int i=2; i<=n; i++) {
            c = Math.min(b+cost[i-1], a+cost[i-2]);
            a = b;
            b = c;
        }
        return c;
    }

    public int minCostClimbingStairs3(int[] cost) {
        int n = cost.length;
        int[] mem = new int[n+1];
        Arrays.fill(mem, -1);
        return dfs3(cost, mem, n);
    }
    private int dfs3(int[] cost, int[] mem, int n) {
        if(n < 2) return 0;
        if (mem[n] ==-1) {
            mem[n] = Math.min(
                    dfs3(cost, mem, n-1)+cost[n-1],
                    dfs3(cost, mem, n-2)+cost[n-2]);
        }
        return mem[n];
    }

    public int minCostClimbingStairs4(int[] cost) {
        int n = cost.length;
        return dfs4(cost, n);
    }
    private int dfs4(int[] cost, int n) {
        if (n < 2) return 0;
        return Math.min(
                dfs4(cost, n-1) + cost[n-1],
                dfs4(cost, n-2) + cost[n-2]);
    }

    @Test
    public void main() {
        System.out.println();
    }
}
